package com.azure.code.graph.topologicalSorting;

import java.util.LinkedList;
import java.util.List;

/**
 * 拓扑排序
 *
 *  <p>
 *  你这个学期必须选修 numCourses 门课程，记为0到numCourses - 1 。
 *  在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites 给出，其中prerequisites[i] = [ai, bi] ，
 *  表示如果要学习课程ai则必须先学习课程bi 。
 *  <br/>
 *  例如，先修课程对[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 *  请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *  </p>
 *  <p>
 *  示例:  <br/>
 *  输入：numCourses = 2, prerequisites = [[1,0]] <br/>
 *  输出：true   <br/>
 *  解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 *  </p>
 *
 *  思路：
 *    转换成有向无环图      图中存在环 说明有循环依赖
 */
public class Courses_207 {
    // 记录一次递归堆栈中的节点
    boolean[] onPath;
    // 记录遍历过的节点，防止走回头路
    boolean[] visited;
    // 记录图中是否有环
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses,prerequisites);
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的而所有节点
            traverse(graph,i);
        }
        // 只要没有循环依赖可以完成所有的课程
        return !hasCycle;
    }

    /**
     * dfs 遍历
     * @param graph 图
     * @param s 节点
     */
    private void traverse(List<Integer>[] graph, int s) {
        if(onPath[s]){
            // 出现环
            hasCycle = true;
        }
        if(visited[s] || hasCycle){
            // 如果已经找到环了，也不用遍历了
            return;
        }
        visited[s] = true;
        onPath[s] = true;
        for (int x : graph[s]) {
            traverse(graph,x);
        }
        onPath[s] = false;
    }


    LinkedList<Integer>[] buildGraph(int num,int[][] prerequisites){
        // 图中共有 num 个节点
        LinkedList<Integer>[] graph = new LinkedList[num];
        for (int i = 0; i < num; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            int from = edge[1],to = edge[0];
            // 添加一条从 from 指向 to 的有向边
            graph[from].add(to);
        }
        return graph;
    }
}
